package com.atguigu.practice;

import java.util.Scanner;

public class AlinenPassword {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt(); //n仅代表数据的组数
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                String s = findXi(a[i] - 1);
                if (s.length() < 4) {
                    int m = 4 - s.length();
                    while (m > 0) {
                        sb.append(0);
                        m--;
                    }
                    sb.append(s);
                } else if (s.length() > 4) { //大于四位只追加最后四位
                    for (int j = s.length() - 4; j < s.length(); j++) {
                        sb.append(s.charAt(j));
                    }
                } else {
                    sb.append(s);
                }
            }
            System.out.println(sb.toString());
        }

    }

    public static String findXi(int n) {
        int[] c = new int[2];
        c[0] = 1;
        c[1] = 1;
        while (n != 0) {
            n--;
            if(c[1]>=1000){
                int tmp=c[0]+c[1];
                c[1]=c[0];
                String s=String.valueOf(tmp);
                String substring = s.substring(s.length() - 4, s.length());
                c[0]=Integer.parseInt(substring);
            }else{
                int tmp=c[0]+c[1];
                c[1]=c[0];
                c[0]=tmp;
            }
        }
        return String.valueOf(c[0]);
    }
}
